package search;

import java.util.ArrayList;

public class Binary {
    public static void main(String[] args) {
        logarithm(1000, 100, 1000);
        runTime(100000, 10000, 1000000);
    }

    /**
     * 二分查找
     *
     * @param array 有序数组
     * @param num   目标数据
     * @return
     */
    public static int binary(ArrayList<Integer> array, int left, int right, int num) {
        if (left > right) {
            return -1;
        }
        int midIndex = (left + right) / 2;
        int midVal = array.get(midIndex);
        if (num == midVal) {
            return midIndex;
        } else if (num < midVal) {
            return binary(array, left, midIndex - 1, num);
        } else {
            return binary(array, midIndex + 1, right, num);
        }
    }

    /**
     * 打印数组
     *
     * @param array
     */
    public static void show(ArrayList<Integer> array) {
        for (int i = 0; i < array.size(); i++) {
            System.out.print(array.get(i) + " ");
        }
        System.out.println();
    }

    /**
     * 产生无重复数据的有序随机数组
     *
     * @param length
     * @return
     */
    public static ArrayList<Integer> getRandomArray(int length, int numRange) {
        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            int num = (int) (Math.random() * numRange);
            while (array.contains(num)) {
                num = (int) (Math.random() * numRange);
            }
            array.add(num);
        }
        array.sort(Integer::compareTo);
        return array;
    }

    /**
     * 对数器
     *
     * @param testNum
     * @param arrayLen
     * @param numRange
     */
    public static void logarithm(int testNum, int arrayLen, int numRange) {
        for (int i = 0; i < testNum; i++) {
            ArrayList<Integer> randomArray = getRandomArray(arrayLen, numRange);
            for (int expectedIndex = 0; expectedIndex < randomArray.size(); expectedIndex++) {
                int actualIndex = binary(randomArray, 0, randomArray.size() - 1, randomArray.get(expectedIndex));
                if (actualIndex != expectedIndex) {
                    show(randomArray);
                    System.out.println("num:" + randomArray.get(expectedIndex) + "\nexpectedIndex:" + expectedIndex + "\nactualIndex:" + actualIndex);
                    return;
                }
            }
        }
        System.out.println("true");
    }

    /**
     * 算法运行时间
     *
     * @param testNum
     * @param arrayLen
     * @param numRange
     */
    public static void runTime(int testNum, int arrayLen, int numRange) {
        ArrayList<Integer> randomArray = getRandomArray(arrayLen, numRange);
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < testNum; i++) {
            int index = (int) (Math.random() * arrayLen);
            binary(randomArray, 0, randomArray.size() - 1, randomArray.get(index));
        }
        long endTime = System.currentTimeMillis();
        long consumingTime = (endTime - startTime);
        System.out.println("startTime:" + startTime + "\nendTime:" + endTime + "\ntestNum：" + testNum + "\tconsumingTime:" + consumingTime);
    }
}
